In many practical applications, it is required to optimize (maximize or minimize) a linear objective function, subject to linear inequality (and sometimes also equality) constraints (also known as Linear Programming (LP)). Given a polytope and a real-value affixed function defined on this polytope, a linear programming method aims to find a point on the polytope where function has the smallest (or largest) value if such a point exists, by searching through the polytope vertices. Information about linear programming and related problems can be found in the publication by T. S. Ferguson, “LINEAR PROGRAMMING, A Concise Introduction”, which is incorporated in its entirety for all purposes as if fully set forth herein
Linear programming problems are commonly expressed in canonical form such as the standard maximum problem: Maximize ctx (=c1x1+ . . . +cnxn) subject to Ax≦b, where x represents the vector of variables (to be determined), c and b are vectors of known coefficients and A is a known matrix (M×N) of coefficients defining the problem. The expression ctx is the objective function to be maximized. The set of inequalities constraints Ax≦b specifies a convex polytope over which the objective function is to be optimized, which implies that every local minimum is a global minimum. Similarly, a linear function is a concave function, thus every local maximum is a global maximum. Similarly, the standard minimum problem is to minimize ytb (=y1b1+ . . . +ymbm) subject to ytA≧ct, where y represents the vector of variables (to be determined), c and b are vectors of known coefficients and A is a known matrix of coefficients defining the problem. The standard minimum problem is defined as the dual of the standard maximum problem, and solving one commonly result in the solution for the other, as ctx=ytb at the optimal point (assuming both problems are feasible).
Linear programming can be applied to various fields, such as business and economics, as well as for engineering. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. LP has been further proven useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.
As part of solving the linear programming problem, and also in many practical problems, it is required to analyze the constraints set Ax≦b, known as the constraints satisfaction problem. Such analysis is required in many problems of artificial intelligence and operation research. For example, it is required to find out if a constraint set is solvable or alternatively if it is infeasible and there is no feasible region. The problem of finding a feasible set to a system of linear inequalities can be formalized as a linear programming problem in which the objective function is the zero function. In another example, it may be useful to find out which of the constraints is not part of the polytope defined by the constraints set (and thus such constraints can be omitted without affecting the solution). Further, it may be useful to find the vertices of the polyhedra defined by the constraints set, since under the convexity assumptions the solution to a linear programming problem is likely to reside in such vertex.
Most current methods for solving constraints satisfaction and linear programming problems involves high complexity calculations, and may require the use of heuristic and combinatorial search methods. Few suggested solving algorithms (such as the simplex algorithm) require limiting the problem, such as requiring that the variables are non-negative or that the right hand side constants b are non-negative. Further, some methods require a known starting feasible point. For example, the simplex algorithm created by the American mathematician George Dantzig is a popular method for solving LP problems, and it is based on the concept of simplex, which is a polytope of N+1 vertices in N dimensions. This boundary method algorithm uses walking along the edges of the polytope to vertices with higher objective function values, until either an optimum extreme point is found or an unbounded edge along which the objective function diverges is found. However, the simplex algorithm assumes that the variables x and the coefficients b are non-negative. Further, the simplex algorithm involves the complexity of inverting matrices of the size of the number of constraints. As such, the complexity is high in case of a large number of constraints.
Other methods, referred to as interior point methods, start with a point in the (relative) interior of the feasible set, and continue in the interior until they reach a near optimal solution. These methods require a feasible point to start from, and thus cannot be applied in cases where such starting point is not known.
Further, in many cases there is no objective function, yet the constraints set needs to be analyzed. For example, it may be required to find out if the constraints set is feasible, or to determine which constraints do not affect the feasible region and can thus be eliminated. Since most algorithms are focusing on the objective function, such methods may not be useful for such analysis of a set of constraints.